693. Минимум в стеке
На вход
программы подается набор операций со стеком. Каждая операция состоит в
добавлении или удалении элемента из стека. После выполнения каждой операции
найдите наименьшее число, которое находится в стеке. Сложите все полученные числа
и получите ответ. Если после некоторой операции стек оказался пуст, то ничего
не прибавляйте к ответу. Если выполнить удаление невозможно, так как стек пуст,
то не выполняйте его.
Вход. Входные данные генерируются в самой программе. На вход
подаются параметры для генерации входной последовательности.
Первое число содержит количество операций n (1 ≤ n ≤ 106) со стеком. Затем следуют четыре
неотрицательных целых числа a, b, c,
x0, не превосходящие
10000.
Для получения входных данных сгенерируем последовательность x.
Первое число в генерируемой последовательности x1. Первое, а также каждое
следующее число вычисляется из предыдущего по формуле:
xi = (a·
+ b·xi-1 + c) / 100 mod 106,
где '/' – операция целочисленного деления, а 'mod' – остаток
от деления.
Если xi
mod 5 < 2, то необходимо удалить число из стека. В противном случае нужно
добавить в стек число xi.
Выход. Выведите
результирующую сумму.
|
Пример
входа 1 |
Пример
выхода 1 |
|
2 0 0 1 81 |
0 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
3 1 1 1 13 |
0 |
РЕШЕНИЕ
структуры
данных - стек
Анализ алгоритма
В задаче
достаточно промоделировать работу со стеком. Если xi mod 5 ≥ 2, то заносить в стек будем не само
очередное значение xi, а
минимум вершины стека и значения xi.
Если стек пустой, то заносим в него xi.
При xi mod 5 < 2
удаляем число из вершины стека. При таком подходе обработки входных данных на
вершине стека всегда будет находиться минимальное значение среди всех обработанных,
но на данный момент еще не удаленных значений xi.
После обработки
очередного значения xi к
результирующей сумме res необходимо
добавить значение, хранящееся в вершине стека.
Реализация алгоритма
Объявим
структуру данных стек.
stack<long
long> s;
Читаем входные
данные.
scanf("%lld %lld %lld %lld %lld",&n,&a,&b,&c,&x);
for(res = i = 0; i < n; i++)
{
В переменной x получаем очередной элемент xi последовательности. В зависимости от значения x mod 5 или кладем в стек минимум
его и значения, находящегося на вершине стека, или удаляем число из вершины
стека.
x = ((a*x*x + b*x + c) / 100) % 1000000;
if (x % 5
< 2)
{
if
(!s.empty()) s.pop();
} else
{
if
(s.empty()) s.push(x);
else
s.push(min(s.top(),x));
}
Если стек не пустой, то прибавляем к
результирующей сумме значение, хранящееся в его вершине.
if (!s.empty()) res += s.top();
}
Выводим ответ.
printf("%lld\n",res);
Реализация стека при помощи статического
массива
Поскольку
количество операций n со стеком не
больше 106, то достаточно использовать стек указанного размера.
#include <stdio.h>
long long
i, n, a, b, c, x, res;
class Stack
{
private:
long long *m;
int topPtr,
size;
void
allocate()
{
m = new long long[size];
topPtr = EmptyStack;
}
public:
enum
{DefaultStack = 1000010, EmptyStack = -1};
Stack()
{
size = DefaultStack;
allocate();
}
Stack(int n)
{
if (!n) n =
DefaultStack;
size = n;
allocate();
}
~Stack()
{
delete[] m;
}
int full(void)
{
return
topPtr + 1 >= size;
}
int empty(void)
{
return
topPtr <= EmptyStack;
}
void push(const long long &Value)
{
if
(!full()) m[++topPtr] = Value;
}
long long pop(void)
{
if
(!empty()) return m[topPtr--];
return 0;
}
long long top(void)
{
if
(!empty()) return m[topPtr];
return 0;
}
};
long long
min(long long
a, long long b)
{
return (a
< b) ? a : b;
}
Stack s;
int main(void)
{
scanf("%lld
%lld %lld %lld %lld",&n,&a,&b,&c,&x);
for(res = i =
0; i < n; i++)
{
x = ((a*x*x + b*x + c) / 100) % 1000000;
if (x % 5
< 2)
{
if
(!s.empty()) s.pop();
} else
{
if
(s.empty()) s.push(x);
else
s.push(min(s.top(),x));
}
if
(!s.empty()) res += s.top();
}
printf("%lld\n",res);
return 0;
}
Реализация стека при помощи динамического
массива
#include <stdio.h>
#include <string.h>
long long
i, n, a, b, c, x, res;
class DynamicArray
{
private:
long long *Storage;
int Size,
Capacity;
public:
DynamicArray(void)
{
Capacity = 10;
Storage = new
long long[Capacity];
memset(Storage,0,sizeof(long long)*Capacity);
Size = 0;
}
DynamicArray(int
Capacity)
{
this->Capacity
= Capacity;
Storage = new
long long[Capacity];
memset(Storage,0,sizeof(long long)*Capacity);
Size = 0;
}
~DynamicArray()
{
delete[]
Storage;
}
int getSize(void)
{
return
Size;
}
int
getCapacity(void)
{
return
Capacity;
}
void Print(void)
{
for(int i = 0; i < Size; i++)
printf("%d
",Storage[i]);
}
void
ensureCapacity(int minCapacity)
{
if
(minCapacity > Capacity)
{
int
newCapacity = (Capacity * 3) / 2 + 1;
if
(newCapacity < minCapacity) newCapacity = minCapacity;
long long *temp = new long long[newCapacity];
memcpy(temp, Storage, Size * sizeof(long long));
delete[]
Storage;
Storage = temp;
Capacity = newCapacity;
}
}
void Pack(void)
{
if (Size
<= Capacity / 2)
{
int
newCapacity = (Size * 3) / 2 + 1;
long long *temp = new long long[newCapacity];
memcpy(temp, Storage, Size * sizeof(long long));
Capacity = newCapacity;
delete[]
Storage;
Storage = temp;
}
}
void Trim(void)
{
int
newCapacity = Size;
long long *temp = new long long[newCapacity];
memcpy(temp, Storage, Size * sizeof(long long));
delete[]
Storage;
Storage = temp;
}
void
SetElement(int index, int
value)
{
if
((index < 0) || (index >= Size)) return;
Storage[index] = value;
}
long long GetElement(int
index)
{
if
((index < 0) || (index >= Size)) return
-1;
return
Storage[index];
}
int Empty(void)
{
return
(Size == 0);
}
void
RemoveAt(int index)
{
if
((index < 0) || (index >= Size)) return;
int
moveCount = Size - index - 1;
if
(moveCount > 0)
{
for(int i = index; i < Size - 1; i++)
Storage[i] = Storage[i+1];
}
Size--;
Pack();
}
void
insertAt(int index, long
long value)
{
if
((index < 0) || (index >= Size)) return;
ensureCapacity(Size + 1);
int
moveCount = Size - index;
if
(moveCount > 0)
{
for(int i = Size - 1; i >= index; i--)
Storage[i+1] = Storage[i];
}
Storage[index] = value;
Size++;
}
void
push_back(long long
Value)
{
ensureCapacity(Size + 1);
Storage[Size] = Value;
Size++;
}
void
pop_back(void)
{
if (Size
== 0) return;
Size--;
Pack();
}
long long back(void)
{
return
Storage[Size-1];
}
};
class Stack
{
private:
DynamicArray m;
public:
Stack()
{
}
int empty(void)
{
return
m.Empty();
}
void push(const long long &Value)
{
m.push_back(Value);
}
void pop(void)
{
if
(!empty()) m.pop_back();
}
long long top(void)
{
if
(!empty()) return m.back();
return 0;
}
};
long long
min(long long
a, long long b)
{
return (a
< b) ? a : b;
}
Stack s;
int main(void)
{
scanf("%lld
%lld %lld %lld %lld",&n,&a,&b,&c,&x);
for(res = i =
0; i < n; i++)
{
x = ((a*x*x + b*x + c) / 100) % 1000000;
if (x % 5
< 2)
{
if (!s.empty())
s.pop();
} else
{
if
(s.empty()) s.push(x);
else
s.push(min(s.top(),x));
}
if
(!s.empty()) res += s.top();
}
printf("%lld\n",res);
return 0;
}
Реализация стека при помощи
связанного списка
#include <stdio.h>
long long
i, n, a, b, c, x, res;
class Stack
{
private:
struct node
{
long long value;
struct node
*next;
};
node *head;
int size;
public:
Stack()
{
size = 0;
head
= NULL;
}
~Stack()
{
while(!empty())
{
node *temp = head;
head = head->next;
delete
temp;
}
}
int empty(void)
{
return
(head == NULL);
}
void push(const long long &Value)
{
node *temp = new
node;
temp->value = Value;
temp->next = head;
head = temp;
}
long long pop(void)
{
if
(!empty())
{
int value
= head->value;
node *temp = head;
head = head->next;
delete
temp;
return
value;
}
return 0;
}
long long top(void)
{
if
(!empty()) return head->value ;
return 0;
}
};
long long
min(long long
a, long long b)
{
return (a
< b) ? a : b;
}
Stack s;
int main(void)
{
scanf("%lld
%lld %lld %lld %lld",&n,&a,&b,&c,&x);
for(res = i =
0; i < n; i++)
{
x = ((a*x*x + b*x + c) / 100) % 1000000;
if (x % 5
< 2)
{
if
(!s.empty()) s.pop();
} else
{
if
(s.empty()) s.push(x);
else
s.push(min(s.top(),x));
}
if
(!s.empty()) res += s.top();
}
printf("%lld\n",res);
return 0;
}
Время работы
программы
|
Статический
массив |
0.250 секунды |
|
Динамический
массив |
0.296 секунды |
|
Динамический
стек на указателях |
0.406 секунды |
|
Стек при
помощи вектора |
0.421 секунды |
|
Использование
класса stack из STL |
0.765 секунды |
Java реализация
import
java.util.*;
public class
Main
{
public static void
main(String[] args)
{
Stack<Long> s = new Stack<Long>();
Scanner con = new
Scanner(System.in);
long n =
con.nextLong();
long a = con.nextLong();
long b =
con.nextLong();
long c =
con.nextLong();
long x =
con.nextLong();
long res =
0;
for(int i = 0; i < n; i++)
{
x = ((a*x*x + b*x + c) / 100) % 1000000;
if (x % 5
< 2)
{
if
(!s.empty())
s.pop();
} else
{
if
(s.empty())
s.push(x);
else
s.push(Math.min(s.peek(),x));
}
if
(!s.empty())
res += s.peek();
}
System.out.println(res);
con.close();
}
}